// 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法.
// n阶楼梯问题(尾递归的优化[函数最后调用自身可以减少中间变量|化递归为循环去优化]/备忘录优化)
function fibonacci(num) {
    if (num <= 0) return
    if (num === 1 || num === 2) return 1;
    return fibonacci(num - 1) + fibonacci(num - 2);
}
console.log(fibonacci(2))


// dp[i]: 第i个斐波拉切数 是下标
// 初始化：
function fibonacci2(num) {
    let arr = [1, 1];
    if (num <= 0) return;
    if (num === 1 || num === 2) return 1;
    for (let i = 2; i < num; i++) {
        arr[i] = arr[i - 1] + arr[i - 2];
    }
    return arr[num - 1];
}
console.log(fibonacci2(2))










function fibonacci3(num) {
    var pre = 1;
    var next = 1;
    if (num <= 0) return;

    for (let i = 2; i < num; i++) {
        let temp = pre;
        pre = next;
        next = pre + temp;
        //或写成：
        //next = pre + next;
        //pre = next - pre;
    }
    return next;
}